{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cheapest Flights Within K Stops"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #dynamic-programming #shortest-path #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #动态规划 #最短路 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findCheapestPrice"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #K 站中转内最便宜的航班"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 个城市通过一些航班连接。给你一个数组&nbsp;<code>flights</code> ，其中&nbsp;<code>flights[i] = [from<sub>i</sub>, to<sub>i</sub>, price<sub>i</sub>]</code> ，表示该航班都从城市 <code>from<sub>i</sub></code> 开始，以价格 <code>price<sub>i</sub></code> 抵达 <code>to<sub>i</sub></code>。</p>\n",
    "\n",
    "<p>现在给定所有的城市和航班，以及出发城市 <code>src</code> 和目的地 <code>dst</code>，你的任务是找到出一条最多经过 <code>k</code>&nbsp;站中转的路线，使得从 <code>src</code> 到 <code>dst</code> 的 <strong>价格最便宜</strong> ，并返回该价格。 如果不存在这样的路线，则输出 <code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> \n",
    "n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]\n",
    "src = 0, dst = 2, k = 1\n",
    "<strong>输出:</strong> 200\n",
    "<strong>解释:</strong> \n",
    "城市航班图如下\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/02/16/995.png\" style=\"height: 180px; width: 246px;\" />\n",
    "\n",
    "从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> \n",
    "n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]\n",
    "src = 0, dst = 2, k = 0\n",
    "<strong>输出:</strong> 500\n",
    "<strong>解释:</strong> \n",
    "城市航班图如下\n",
    "<img alt=\"\" src=\"https://s3-lc-upload.s3.amazonaws.com/uploads/2018/02/16/995.png\" style=\"height: 180px; width: 246px;\" />\n",
    "\n",
    "从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，如图中蓝色所示。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "\t<li><code>0 &lt;= flights.length &lt;= (n * (n - 1) / 2)</code></li>\n",
    "\t<li><code>flights[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= from<sub>i</sub>, to<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>from<sub>i</sub> != to<sub>i</sub></code></li>\n",
    "\t<li><code>1 &lt;= price<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>航班没有重复，且不存在自环</li>\n",
    "\t<li><code>0 &lt;= src, dst, k &lt; n</code></li>\n",
    "\t<li><code>src != dst</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cheapest-flights-within-k-stops](https://leetcode.cn/problems/cheapest-flights-within-k-stops/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cheapest-flights-within-k-stops](https://leetcode.cn/problems/cheapest-flights-within-k-stops/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]]\\n0\\n3\\n1', '3\\n[[0,1,100],[1,2,100],[0,2,500]]\\n0\\n2\\n1', '3\\n[[0,1,100],[1,2,100],[0,2,500]]\\n0\\n2\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:\n",
    "        f = [[float(\"inf\")] * n for _ in range(k + 2)]\n",
    "        f[0][src] = 0\n",
    "        for t in range(1, k + 2):\n",
    "            for j, i, cost in flights:\n",
    "                f[t][i] = min(f[t][i], f[t - 1][j] + cost)\n",
    "\n",
    "        answer = min(f[t][dst] for t in range(1, k + 2))\n",
    "        return -1 if answer == float(\"inf\") else answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        # predecessor\n",
    "        # successor\n",
    "        dp = [[float(\"inf\")] * (k+2) for _ in range(n)]\n",
    "        dp[src][0] = 0\n",
    "        for i in range(1, k+2):\n",
    "            for f, t, price in flights:\n",
    "                dp[t][i] = min(dp[t][i], dp[f][i-1]+price)\n",
    "        res = min([dp[dst][i] for i in range(0, k+2)])\n",
    "        return -1 if res == float(\"inf\") else res\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, tgt: int, k: int) -> int:\n",
    "        dp = [inf for _ in range(n)]\n",
    "        dp[src] = 0\n",
    "        for _ in range(k + 1):\n",
    "            tmp = dp.copy()\n",
    "            for x, y, w in flights:\n",
    "                dp[y] = min(dp[y], tmp[x] + w)\n",
    "        return -1 if dp[tgt] == inf else dp[tgt]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: list[list[int]], src: int, dst: int, k: int) -> int:\n",
    "        f = [[float(\"inf\")] * n for _ in range(k + 2)]\n",
    "        f[0][src] = 0\n",
    "        for t in range(1, k + 2):\n",
    "            for j, i, cost in flights:\n",
    "                f[t][i] = min(f[t][i], f[t - 1][j] + cost)\n",
    "\n",
    "        answer = min(f[t][dst] for t in range(1, k + 2))\n",
    "        return -1 if answer == float(\"inf\") else answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        # 城市A到城市B的所有线路 需要的价格和航程数\n",
    "        price_one = [[False]*n for i in range(n)]#单次的\n",
    "        for s,d,p in flights:\n",
    "            price_one[s][d] = p\n",
    "        \n",
    "        # dp[i][j][kk]# 经过kk次以内的中转，从[i]到[j]的最小花费\n",
    "        # min(dp[i][m][kk-1] + dp[m][j][0] + 1) 遍历m\n",
    "        dp = [[False]*n for i in range(n)]\n",
    "        dp_new = [[False]*n for i in range(n)]\n",
    "        for s,d,p in flights:\n",
    "            dp[s][d] = p\n",
    "            dp_new[s][d] = p\n",
    "\n",
    "        for kk in range(k):\n",
    "            #print(f'{kk}次中转')\n",
    "            for ds in range(n):#最终目的地\n",
    "                #print(f'更新目的地{ds}')                \n",
    "                for m in range(n):#中介\n",
    "                    if dp[src][m] and price_one[m][ds]:                        \n",
    "                        zz = dp[src][m] + price_one[m][ds]\n",
    "                        #print(f'{src}经过{m}中转到{ds}，需花费{zz},原花费{dp[src][ds]}')\n",
    "                        if dp_new[src][ds]:#可能是False# \n",
    "                        #应该对m里的求min，因为可能有很多个zz，zz之间还没比较\n",
    "                            dp_new[src][ds] = min(dp_new[src][ds], zz)#dp_都有，dp_new一定有\n",
    "                        else:\n",
    "                            dp_new[src][ds] = zz\n",
    "            #新增中转结束，更新dp\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    dp[i][j] = dp_new[i][j]\n",
    "        if dp[src][dst]:\n",
    "            return dp[src][dst]\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        INF = 10**6\n",
    "        dist = [INF] * n\n",
    "        dist[src] = 0\n",
    "\n",
    "        for _ in range(k + 1):\n",
    "            dist_cpy = list(dist)\n",
    "            for u, v, w in flights:\n",
    "                dist_cpy[v] = min(dist_cpy[v], dist[u] + w)\n",
    "            \n",
    "            dist = dist_cpy\n",
    "        \n",
    "        return -1 if dist[dst] == INF else dist[dst]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\r\n",
    "        # dic = {}\r\n",
    "        # for v in flights:\r\n",
    "        #     if v[0] in dic:\r\n",
    "        #         dic[v[0]].append((v[1], v[2]))\r\n",
    "        #     else:\r\n",
    "        #         dic[v[0]] = [(v[1], v[2])]\r\n",
    "        # ans = float('inf')\r\n",
    "\r\n",
    "        # def dfs(stc, cur, num):\r\n",
    "        #     nonlocal ans\r\n",
    "        #     if num > k or cur >= ans:\r\n",
    "        #         return\r\n",
    "        #     if stc == dst:\r\n",
    "        #         ans = min(ans, cur)\r\n",
    "        #         return\r\n",
    "        #     if stc in dic:\r\n",
    "        #         for key in dic[stc]:\r\n",
    "        #             dfs(key[0], cur + key[1], num + 1)\r\n",
    "\r\n",
    "        # dfs(src, 0, -1)\r\n",
    "        # if ans == float('inf'):\r\n",
    "        #     return(-1)\r\n",
    "        # return(ans)\r\n",
    "\r\n",
    "        lat = [float('inf') for _ in range(n)]\r\n",
    "        for s, d, p in flights:\r\n",
    "            # 初始化所有src零中转所能到达的机场\r\n",
    "            if s == src:\r\n",
    "                lat[d] = p\r\n",
    "        \r\n",
    "        for _ in range(1, k + 1):\r\n",
    "            nex = [float('inf') for _ in range(n)]\r\n",
    "            for s, d, p in flights:\r\n",
    "                nex[d] = min(nex[d], lat[d], lat[s] + p)\r\n",
    "            lat = nex\r\n",
    "        return(lat[dst] if lat[dst] != float('inf') else -1)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        # w = [[inf] * n for _ in range(n)]\n",
    "        # for i in range(n):\n",
    "        #     w[i][i] = 0\n",
    "        # for u, v, c in flights:\n",
    "        #     w[u][v] = c\n",
    "\n",
    "        # # 最多 k 站中转对应最多（k+1）条边\n",
    "        # dp = [[inf] * n for _ in range(2)]\n",
    "        # dp[0][src] = 0\n",
    "        # for i in range(1, k+2):\n",
    "        #     for v in range(n):\n",
    "        #         c = inf\n",
    "        #         for u in range(n):\n",
    "        #             if w[u][v] < inf:\n",
    "        #                 c = min(c, dp[(i-1) % 2][u] + w[u][v])\n",
    "        #         dp[i % 2][v] = min(dp[i % 2][v], c)\n",
    "        # return dp[(k+1) % 2][dst] if dp[(k+1) % 2][dst] < inf else -1\n",
    "\n",
    "        f = [[inf] * n for _ in range(2)]\n",
    "        f[0][src] = f[1][src] = 0\n",
    "        for i in range(1, k+2):\n",
    "            for u, v, w in flights:\n",
    "                if f[(i-1) % 2][u] + w < f[i % 2][v]:\n",
    "                    f[i % 2][v] = f[(i-1) % 2][u] + w\n",
    "            if f[0] == f[1]:\n",
    "                break\n",
    "        return f[(k+1) % 2][dst] if f[(k+1) % 2][dst] < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        INF = float(\"inf\")\n",
    "        dp = [[INF] * n for _ in range(k + 2)]; dp[0][src] = 0\n",
    "        for i in range(1, k + 2):\n",
    "            for flight in flights:\n",
    "                f, t, p = flight\n",
    "                dp[i][t] = min(dp[i][t], dp[i - 1][f] + p)\n",
    "        res = INF\n",
    "        for i in range(k + 2):\n",
    "            res = min(res, dp[i][dst])\n",
    "        return res if res != INF else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        # f = [[float('inf')] * n for _ in range(k+2)]\n",
    "        # f[0][src] = 0\n",
    "        # for t in range(1, k + 2):\n",
    "        #     for j, i, cost in flights:\n",
    "        #         f[t][i] = min(f[t][i], f[t-1][j] + cost)\n",
    "\n",
    "        # ans = min(f[t][dst] for t in range(1, k+2))\n",
    "        # return -1 if ans == float('inf') else ans\n",
    "\n",
    "        f = [float('inf')] * n\n",
    "        f[src] = 0\n",
    "        ans = float('inf')\n",
    "        for t in range(1, k+2):\n",
    "            g = [float('inf')] * n\n",
    "            for j, i, cost in flights:\n",
    "                g[i] = min(g[i], f[j] + cost)\n",
    "            f = g\n",
    "            ans = min(ans,f[dst])\n",
    "        return -1 if ans == float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        adjMatrix = [[-1] * n for _ in range(n)]\n",
    "        for flight in flights:\n",
    "            adjMatrix[flight[0]][flight[1]] = flight[2]\n",
    "            pass\n",
    "        # 初始化为 恰好经过一次航班的最便宜价格\n",
    "        dp = [i for i in adjMatrix[src]]\n",
    "        minDst = dp[dst]\n",
    "        for t in range(2, k + 2):\n",
    "            tmp = [-1] * n\n",
    "            for i in range(n):\n",
    "                for j in range(n):\n",
    "                    if dp[j] != -1 and adjMatrix[j][i] != -1:\n",
    "                        if tmp[i] == -1:\n",
    "                            tmp[i] = dp[j] + adjMatrix[j][i]\n",
    "                            pass\n",
    "                        else:\n",
    "                            tmp[i] = min(tmp[i], dp[j] + adjMatrix[j][i])\n",
    "                            pass\n",
    "                        pass\n",
    "                    pass\n",
    "                pass\n",
    "            if minDst == -1:\n",
    "                minDst = tmp[dst]\n",
    "                pass\n",
    "            elif tmp[dst] != -1:\n",
    "                minDst = min(minDst, tmp[dst])\n",
    "            dp = tmp\n",
    "            pass\n",
    "        return minDst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        f=[[float('inf')]*n for _ in range(k+2)]\n",
    "        f[0][src]=0\n",
    "        for t in range(1,k+2):\n",
    "            for j,i,cost in flights:\n",
    "                f[t][i]=min(f[t][i],f[t-1][j]+cost)\n",
    "        ans=min(f[t][dst] for t in range(1,k+2))\n",
    "        return -1 if ans==float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        inf = 1e9\n",
    "        dist = [inf] * n\n",
    "        dist[src] = 0\n",
    "        for i in range(k + 1):\n",
    "            clone = dist.copy()\n",
    "            for t in flights:\n",
    "                a = t[0]\n",
    "                b = t[1]\n",
    "                c = t[2]\n",
    "                if dist[b] > clone[a] + c:\n",
    "                    dist[b] = clone[a] + c\n",
    "\n",
    "        if dist[dst] > inf / 2:\n",
    "            return -1\n",
    "        return dist[dst]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self,n, flights, src, dst, k):\n",
    "        INF = float('inf')\n",
    "        dp = [[INF] * n for _ in range(k + 2)]\n",
    "\n",
    "        for t in range(k + 2):\n",
    "            dp[t][src] = 0\n",
    "\n",
    "        for t in range(1, k + 2):\n",
    "            for i, j, price in flights:\n",
    "                dp[t][j] = min(dp[t][j], dp[t - 1][i] + price)\n",
    "\n",
    "        result = dp[k + 1][dst]\n",
    "        return result if result != INF else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.memo = []\n",
    "        self.indegree = {}\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        k +=1\n",
    "        self.memo = [[-1] *(k+1) for _ in range(n)]\n",
    "        indegree = {}\n",
    "        for f in flights:\n",
    "            from_, to, price = f\n",
    "            if to not in self.indegree:\n",
    "                self.indegree[to] = []\n",
    "            self.indegree[to].append([from_, price])\n",
    "        self.src = src\n",
    "        return self.dp(dst,k)\n",
    "    def dp(self,s,k):\n",
    "        if s == self.src:\n",
    "            return 0\n",
    "        if k ==0:\n",
    "            return -1\n",
    "        if self.memo[s][k] != -1:\n",
    "            return self.memo[s][k]\n",
    "        res = float('inf')\n",
    "        if s in self.indegree:\n",
    "            for v in self.indegree[s]:\n",
    "                from_,price = v\n",
    "                sub_problem = self.dp(from_,k-1)\n",
    "                if sub_problem !=-1:\n",
    "                    res = min(res, sub_problem+price)\n",
    "        self.memo[s][k] = -1 if res == float('inf') else res\n",
    "        return self.memo[s][k]\n",
    "    \n",
    "                \n",
    "\n",
    "\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        g = [[] for i in range(n)]\n",
    "        for i, j, m in flights:\n",
    "            g[i].append((j, m))\n",
    "        \n",
    "        vis = {src: 0}\n",
    "        queue = deque([(0, src)])\n",
    "        while queue:\n",
    "            for i in range(len(queue)):\n",
    "                wei, node = queue.popleft()\n",
    "                for a, b in g[node]:\n",
    "                    w = wei + b\n",
    "                    if a not in vis or w < vis[a]:\n",
    "                        vis[a] = w\n",
    "                        queue.append((w, a))\n",
    "\n",
    "            k -= 1\n",
    "            if k == -1:\n",
    "                break\n",
    "        \n",
    "        if dst in vis:\n",
    "            return vis[dst]\n",
    "        return -1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\r\n",
    "        # dic = {}\r\n",
    "        # for v in flights:\r\n",
    "        #     if v[0] in dic:\r\n",
    "        #         dic[v[0]].append((v[1], v[2]))\r\n",
    "        #     else:\r\n",
    "        #         dic[v[0]] = [(v[1], v[2])]\r\n",
    "        # ans = float('inf')\r\n",
    "\r\n",
    "        # visited = [False for i in range(n)]\r\n",
    "        # visited[src] = True\r\n",
    "        # def dfs(stc, cur, num):\r\n",
    "        #     nonlocal ans\r\n",
    "        #     if num > k or cur >= ans:\r\n",
    "        #         return\r\n",
    "        #     if stc == dst:\r\n",
    "        #         ans = min(ans, cur)\r\n",
    "        #         return\r\n",
    "        #     if stc in dic:\r\n",
    "        #         for key in dic[stc]:\r\n",
    "        #             if not visited[key[0]]:\r\n",
    "        #                 visited[key[0]] = True\r\n",
    "        #                 dfs(key[0], cur + key[1], num + 1)\r\n",
    "        #                 visited[key[0]] = False\r\n",
    "\r\n",
    "        # dfs(src, 0, -1)\r\n",
    "        # if ans == float('inf'):\r\n",
    "        #     return(-1)\r\n",
    "        # return(ans)\r\n",
    "        dp = [[float('inf') for __ in range(n)] for _ in range(k + 1)]\r\n",
    "        for s, d, p in flights:\r\n",
    "            if s == src:\r\n",
    "                dp[0][d] = p\r\n",
    "        \r\n",
    "        for i in range(1, k + 1):\r\n",
    "            for s, d, p in flights:\r\n",
    "                dp[i][d] = min(dp[i][d], dp[i - 1][d], dp[i - 1][s] + p)\r\n",
    "        return(dp[k][dst] if dp[k][dst] != float('inf') else -1)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\r\n",
    "        # dic = {}\r\n",
    "        # for v in flights:\r\n",
    "        #     if v[0] in dic:\r\n",
    "        #         dic[v[0]].append((v[1], v[2]))\r\n",
    "        #     else:\r\n",
    "        #         dic[v[0]] = [(v[1], v[2])]\r\n",
    "        # ans = float('inf')\r\n",
    "\r\n",
    "        # visited = [False for i in range(n)]\r\n",
    "        # visited[src] = True\r\n",
    "        # def dfs(stc, cur, num):\r\n",
    "        #     nonlocal ans\r\n",
    "        #     if num > k or cur >= ans:\r\n",
    "        #         return\r\n",
    "        #     if stc == dst:\r\n",
    "        #         ans = min(ans, cur)\r\n",
    "        #         return\r\n",
    "        #     if stc in dic:\r\n",
    "        #         for key in dic[stc]:\r\n",
    "        #             if not visited[key[0]]:\r\n",
    "        #                 visited[key[0]] = True\r\n",
    "        #                 dfs(key[0], cur + key[1], num + 1)\r\n",
    "        #                 visited[key[0]] = False\r\n",
    "\r\n",
    "        # dfs(src, 0, -1)\r\n",
    "        # if ans == float('inf'):\r\n",
    "        #     return(-1)\r\n",
    "        # return(ans)\r\n",
    "        dp = [[float('inf') for __ in range(n)] for _ in range(k + 1)]\r\n",
    "        for s, d, p in flights:\r\n",
    "            if s == src:\r\n",
    "                dp[0][d] = p\r\n",
    "        \r\n",
    "        for i in range(1, k + 1):\r\n",
    "            for s, d, p in flights:\r\n",
    "                dp[i][d] = min(dp[i][d], dp[i - 1][d], dp[i - 1][s] + p)\r\n",
    "        return(dp[k][dst] if dp[k][dst] != float('inf') else -1)\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        distance = [10**9]*n\n",
    "        distance[src] = 0\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for edge in flights:\n",
    "            edges[edge[1]].append((edge[0],edge[2]))\n",
    "        for i in range(k+1):\n",
    "            t_flag = True\n",
    "            temp = [num for num in distance]\n",
    "            for j in range(n):\n",
    "                for edge in edges[j]:\n",
    "                    if temp[edge[0]]+edge[1]<min(temp[j],distance[j]):\n",
    "                        distance[j] = temp[edge[0]]+edge[1]\n",
    "                        t_flag =False\n",
    "            if t_flag:\n",
    "                break\n",
    "        res = distance[dst]\n",
    "        return -1 if res==10**9 else res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "\n",
    "        graph = defaultdict(list)\n",
    "        for a, b, p in flights:\n",
    "            graph[a].append([b, p])\n",
    "\n",
    "        cur_layer = {src: 0} # <到节点需要累计成本>:<节点>\n",
    "        # to_visit = set(range(1, n+1)) - {src}\n",
    "        min_distance = [float('inf')] * n # 记录src到当前节点的最短距离\n",
    "        ans = float('inf')\n",
    "        while cur_layer and k > -2:\n",
    "            next_layer = {}\n",
    "            # print(f'{cur_layer} k {k}')\n",
    "            for node, base_price in cur_layer.items():\n",
    "                if node == dst:\n",
    "                    min_distance[node-1] = min(min_distance[node-1], base_price)\n",
    "                    continue\n",
    "                if node not in graph: # 没有后续节点\n",
    "                    continue\n",
    "                if k == -1: # 不需要检查后续节点\n",
    "                    continue\n",
    "                for next_node, ticket_price in graph[node]:\n",
    "                    if min_distance[next_node] != float('inf') and base_price+ticket_price >= min_distance[next_node]: # 已知更短路径到next_node\n",
    "                        continue\n",
    "                    # 同层节点更新\n",
    "                    if next_node not in next_layer:\n",
    "                        next_layer[next_node] = base_price+ticket_price\n",
    "                    else:\n",
    "                        next_layer[next_node] = min(next_layer[next_node], base_price+ticket_price)\n",
    "                # for next_node, _ in graph[node]:\n",
    "                #     if next_node != dst:\n",
    "                #         to_visit.discard(next_node)\n",
    "            cur_layer = next_layer\n",
    "            k -= 1\n",
    "        return -1 if min_distance[dst-1] == float('inf') else min_distance[dst-1]\n",
    "        # return -1 if ans == float('inf') else ans\n",
    "\n",
    "\n",
    "        # def dfs(price, node, k):\n",
    "        #     # print(f'price {price}, node {node}, k {k}')\n",
    "        #     nonlocal ans\n",
    "        #     if price > ans or k < 0:\n",
    "        #         return\n",
    "        #     if node == dst:\n",
    "        #         ans = price\n",
    "        #         return\n",
    "        #     if node not in graph:\n",
    "        #         return\n",
    "        #     visited.add(node)\n",
    "        #     for next_node, ticket_price in graph[node]:\n",
    "        #         if next_node not in visited:\n",
    "        #             dfs(price+ticket_price, next_node, k-1)\n",
    "        #     visited.discard(node)\n",
    "        \n",
    "        # graph = defaultdict(list)\n",
    "        # for a, b, p in flights:\n",
    "        #     graph[a].append([b, p])\n",
    "        \n",
    "        # ans = float('inf')\n",
    "        # visited = set()\n",
    "        # dfs(0, src, k+1)\n",
    "        # return -1 if ans == float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        source = defaultdict(list)\n",
    "        for flight in flights:\n",
    "            source[flight[1]].append([flight[0], flight[2]])\n",
    "        # -9999表示未计算，-1表示不可达\n",
    "        dp = [[-9999] * (k + 2) for _ in range(n)]\n",
    "        return self.helper(flights, source, src, dp, dst, k + 1, dst)\n",
    "    \n",
    "    def helper(self, flights, source, src, dp, dst, k, cur):\n",
    "        if cur == src:\n",
    "            return 0\n",
    "        if k == 0:\n",
    "            return -1\n",
    "        if dp[cur][k] != -9999:\n",
    "            return dp[cur][k]\n",
    "        res = float(\"inf\")\n",
    "        for to_from in source[cur]:\n",
    "            from_ = to_from[0]\n",
    "            price = to_from[1]\n",
    "            subProblem = self.helper(flights, source, src, dp, dst, k - 1, from_)\n",
    "            if subProblem != -1:\n",
    "                res = min(res, subProblem + price)\n",
    "        dp[cur][k] = -1 if res == float(\"inf\") else res\n",
    "        return dp[cur][k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from math import *\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        cost=[inf]*n\n",
    "        cost[src]=0\n",
    "        edges=defaultdict(list)\n",
    "        for [u,v,p] in flights:\n",
    "            edges[u].append((v,p))\n",
    "        q=[]\n",
    "        for v,p in edges[src]:\n",
    "            q.append(v)\n",
    "            cost[v]=min(cost[v],cost[src]+p)\n",
    "        for _ in range(k):\n",
    "            ncost=defaultdict(lambda:inf)\n",
    "            while q:\n",
    "                u=q.pop()\n",
    "                for v,p in edges[u]:\n",
    "                    ncost[v]=min(ncost[v],cost[u]+p)\n",
    "            for v,p in ncost.items():\n",
    "                q.append(v)\n",
    "                cost[v]=min(cost[v],p)\n",
    "        ans=cost[dst]\n",
    "        return -1 if isinf(ans) else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-er-zhan-a01c6/yong-dong--63ceb/lv-you-she-f3b76/\n",
    "# 这题就是个加权有向图中求最短路径的问题。\n",
    "# 说白了，就是给你一幅加权有向图，让你求 src 到 dst 权重最小的一条路径，同时要满足，这条路径最多不能超过 K + 1 条边（经过 K 个节点相当于经过 K + 1 条边）\n",
    "\n",
    "# 求最短路径，肯定可以用 BFS 算法来解决。\n",
    "# 但对于加权图，路径中边的条数和路径的权重并不是正相关的关系了，有的路径可能边的条数很少，但每条边的权重都很大，那显然这条路径权重也会很大，很难成为最短路径\n",
    "# 对于加权图的场景，我们需要优先级队列「自动排序」的特性，将路径权重较小的节点排在队列前面，以此为基础施展 BFS 算法，也就变成了 Dijkstra 算法\n",
    "\n",
    "# 但此题用动规来解决。求最值，用动规\n",
    "# 看不懂没事，考的概率很小。虽然我当前看懂了\n",
    "# dp函数定义：截止到当前节点位置为止，从最开始的起点到当前节点，最小权重是多少。当然题目中，是倒序的，倒着一步步推向最开始的起点位置\n",
    "# 暴力解，超时。但是就掌握这种方法把\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "#         def dp(s, k):\n",
    "#             # base case 1\n",
    "#             if s == src:\n",
    "#                 return 0\n",
    "#             # base case 2\n",
    "#             if k <= 0:\n",
    "#                 return -1\n",
    "            \n",
    "#             # 状态转移\n",
    "#             res = float(\"inf\")\n",
    "            \n",
    "#             if s in indegree:\n",
    "#                 for s_, p_ in indegree[s]:\n",
    "#                     # 这里是k-1，在递归过程中k会一直减少，最后会减少到0.这说明是倒着递归的。\n",
    "#                     # 倒着递归，终点时候就走了k个中转站，一直走到最开始的起点，就是走了0个中转站\n",
    "#                     sub_problem = dp(s_, k-1)\n",
    "#                     if sub_problem != -1:\n",
    "#                         res = min(res, sub_problem + p_)\n",
    "            \n",
    "#             # 如果还是初始值，说明此节点不可达\n",
    "#             return res if res != float(\"inf\") else -1\n",
    "\n",
    "\n",
    "#         # 我希望给一个节点，就能知道有谁指向这个节点，还知道它们之间的权重，对吧。\n",
    "#         # 专业点说，得用一个数据结构记录每个节点的「入度」indegree：\n",
    "#         indegree = defaultdict(list)\n",
    "#         for src_, dst_, price_ in flights:\n",
    "#             indegree[dst_].append([src_, price_])\n",
    "        \n",
    "#         k = k + 1 # k+1条边\n",
    "        \n",
    "#         memo = [-1] * n\n",
    "\n",
    "#         return dp(dst, k) # 倒序的嘛，从终点向起点倒着递归\n",
    "\n",
    "\n",
    "\n",
    "# 方法二：备忘录\n",
    "# 谁在变化？显然就是 dp 函数的参数 s 和 k，每次递归调用，目标点 s 和步数约束 k 在变化。\n",
    "# 所以，本题的状态有两个，应该算是二维动态规划，我们可以用一个 memo 二维数组或者哈希表作为备忘录，减少重复计算\n",
    "# 选用二维数组做备忘录吧，注意 K 是从 1 开始算的，所以备忘录初始大小要再加一\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        def dp(s, k):\n",
    "            # base case 1\n",
    "            if s == src:\n",
    "                return 0\n",
    "            # base case 2\n",
    "            if k <= 0:\n",
    "                return -1\n",
    "            \n",
    "            # 消除子问题\n",
    "            if memo[s][k] != -1:\n",
    "                return memo[s][k]\n",
    "            \n",
    "            # 状态转移\n",
    "            res = float(\"inf\")\n",
    "            \n",
    "            if s in indegree:\n",
    "                for s_, p_ in indegree[s]:\n",
    "                    # 这里是k-1，在递归过程中k会一直减少，最后会减少到0.这说明是倒着递归的。\n",
    "                    # 倒着递归，终点时候就走了k个中转站，一直走到最开始的起点，就是走了0个中转站\n",
    "                    sub_problem = dp(s_, k-1)\n",
    "                    if sub_problem != -1:\n",
    "                        res = min(res, sub_problem + p_)\n",
    "            \n",
    "            # 如果还是初始值，说明此节点不可达\n",
    "            memo[s][k] = res if res != float('inf') else -1\n",
    "            return memo[s][k]\n",
    "\n",
    "\n",
    "        # 我希望给一个节点，就能知道有谁指向这个节点，还知道它们之间的权重，对吧。\n",
    "        # 专业点说，得用一个数据结构记录每个节点的「入度」indegree：\n",
    "        indegree = defaultdict(list)\n",
    "        for src_, dst_, price_ in flights:\n",
    "            indegree[dst_].append([src_, price_])\n",
    "        \n",
    "        k = k + 1 # k+1条边\n",
    "        \n",
    "        # 选用二维数组做备忘录吧，注意 K 是从 1 开始算的，所以备忘录初始大小要再加一。k+1最小就是1，所以k从1开始计数的\n",
    "        memo = [[-1] * (k+1) for _ in range(n)]\n",
    "\n",
    "        return dp(dst, k) # 倒序的嘛，从终点向起点倒着递归\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "\n",
    "        dct = defaultdict(dict)\n",
    "        for a, b, p in flights:\n",
    "            dct[a][b] = p\n",
    "\n",
    "        visit = [n+1]*n\n",
    "        stack = [[0, src, 0]]\n",
    "        heapq.heapify(stack)\n",
    "        while stack:\n",
    "            cost, pos, cnt = heapq.heappop(stack)\n",
    "            if pos == dst:\n",
    "                return cost\n",
    "            if cnt >= visit[pos] or cnt > k:\n",
    "                continue\n",
    "            visit[pos] = cnt\n",
    "            for nex in dct[pos]:\n",
    "                heapq.heappush(stack, [cost+dct[pos][nex], nex, cnt+1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        #堆优化的单源最短路算法\n",
    "        dct = defaultdict(dict)\n",
    "        for a, b, p in flights:\n",
    "            dct[a][b] = p\n",
    "\n",
    "        visit = [n+1]*n\n",
    "        stack = [[0, src, 0]]\n",
    "        heapq.heapify(stack)\n",
    "        while stack:\n",
    "            cost, pos, cnt = heapq.heappop(stack)\n",
    "            if pos == dst:\n",
    "                return cost\n",
    "            if cnt >= visit[pos] or cnt > k:\n",
    "                continue\n",
    "            visit[pos] = cnt\n",
    "            for nex in dct[pos]:\n",
    "                heapq.heappush(stack, [cost+dct[pos][nex], nex, cnt+1])\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u,v,w in flights:\n",
    "            graph[u].append((v, w))\n",
    "        visited = [n + 1] * n\n",
    "        heap = [(0, src, 0)]\n",
    "        while heap:\n",
    "            w, u, c = heapq.heappop(heap)\n",
    "            if u == dst:\n",
    "                return w\n",
    "            if c > k or c >= visited[u]:\n",
    "                continue\n",
    "            visited[u] = c\n",
    "            for v, price in graph[u]:\n",
    "                heapq.heappush(heap, (w + price, v, c + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-er-zhan-a01c6/yong-dong--63ceb/lv-you-she-f3b76/\n",
    "# 这题就是个加权有向图中求最短路径的问题。\n",
    "# 说白了，就是给你一幅加权有向图，让你求 src 到 dst 权重最小的一条路径，同时要满足，这条路径最多不能超过 K + 1 条边（经过 K 个节点相当于经过 K + 1 条边）\n",
    "\n",
    "# 求最短路径，肯定可以用 BFS 算法来解决。\n",
    "# 但对于加权图，路径中边的条数和路径的权重并不是正相关的关系了，有的路径可能边的条数很少，但每条边的权重都很大，那显然这条路径权重也会很大，很难成为最短路径\n",
    "# 对于加权图的场景，我们需要优先级队列「自动排序」的特性，将路径权重较小的节点排在队列前面，以此为基础施展 BFS 算法，也就变成了 Dijkstra 算法\n",
    "\n",
    "# 但此题用动规来解决。求最值，用动规\n",
    "# 看不懂没事，考的概率很小。虽然我当前看懂了\n",
    "# dp函数定义：截止到当前节点位置为止，从最开始的起点到当前节点，最小权重是多少。当然题目中，是倒序的，倒着一步步推向最开始的起点位置\n",
    "# 暴力解，超时\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "#         def dp(s, k):\n",
    "#             # base case 1\n",
    "#             if s == src:\n",
    "#                 return 0\n",
    "#             # base case 2\n",
    "#             if k <= 0:\n",
    "#                 return -1\n",
    "            \n",
    "#             # 状态转移\n",
    "#             res = float(\"inf\")\n",
    "            \n",
    "#             if s in indegree:\n",
    "#                 for s_, p_ in indegree[s]:\n",
    "#                     # 这里是k-1，在递归过程中k会一直减少，最后会减少到0.这说明是倒着递归的。\n",
    "#                     # 倒着递归，终点时候就走了k个中转站，一直走到最开始的起点，就是走了0个中转站\n",
    "#                     sub_problem = dp(s_, k-1)\n",
    "#                     if sub_problem != -1:\n",
    "#                         res = min(res, sub_problem + p_)\n",
    "            \n",
    "#             # 如果还是初始值，说明此节点不可达\n",
    "#             return res if res != float(\"inf\") else -1\n",
    "\n",
    "\n",
    "#         # 我希望给一个节点，就能知道有谁指向这个节点，还知道它们之间的权重，对吧。\n",
    "#         # 专业点说，得用一个数据结构记录每个节点的「入度」indegree：\n",
    "#         indegree = defaultdict(list)\n",
    "#         for src_, dst_, price_ in flights:\n",
    "#             indegree[dst_].append([src_, price_])\n",
    "        \n",
    "#         k = k + 1 # k+1条边\n",
    "        \n",
    "#         memo = [-1] * n\n",
    "\n",
    "#         return dp(dst, k) # 倒序的嘛，从终点向起点倒着递归\n",
    "\n",
    "\n",
    "\n",
    "# 方法二：备忘录\n",
    "# 谁在变化？显然就是 dp 函数的参数 s 和 k，每次递归调用，目标点 s 和步数约束 k 在变化。\n",
    "# 所以，本题的状态有两个，应该算是二维动态规划，我们可以用一个 memo 二维数组或者哈希表作为备忘录，减少重复计算\n",
    "# 选用二维数组做备忘录吧，注意 K 是从 1 开始算的，所以备忘录初始大小要再加一\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        def dp(s, k):\n",
    "            # base case 1\n",
    "            if s == src:\n",
    "                return 0\n",
    "            # base case 2\n",
    "            if k <= 0:\n",
    "                return -1\n",
    "            \n",
    "            # 消除子问题\n",
    "            if memo[s][k] != -1:\n",
    "                return memo[s][k]\n",
    "            \n",
    "            # 状态转移\n",
    "            res = float(\"inf\")\n",
    "            \n",
    "            if s in indegree:\n",
    "                for s_, p_ in indegree[s]:\n",
    "                    # 这里是k-1，在递归过程中k会一直减少，最后会减少到0.这说明是倒着递归的。\n",
    "                    # 倒着递归，终点时候就走了k个中转站，一直走到最开始的起点，就是走了0个中转站\n",
    "                    sub_problem = dp(s_, k-1)\n",
    "                    if sub_problem != -1:\n",
    "                        res = min(res, sub_problem + p_)\n",
    "            \n",
    "            # 如果还是初始值，说明此节点不可达\n",
    "            memo[s][k] = res if res != float('inf') else -1\n",
    "            return memo[s][k]\n",
    "\n",
    "\n",
    "        # 我希望给一个节点，就能知道有谁指向这个节点，还知道它们之间的权重，对吧。\n",
    "        # 专业点说，得用一个数据结构记录每个节点的「入度」indegree：\n",
    "        indegree = defaultdict(list)\n",
    "        for src_, dst_, price_ in flights:\n",
    "            indegree[dst_].append([src_, price_])\n",
    "        \n",
    "        k = k + 1 # k+1条边\n",
    "        \n",
    "        # 选用二维数组做备忘录吧，注意 K 是从 1 开始算的，所以备忘录初始大小要再加一。k+1最小就是1，所以k从1开始计数的\n",
    "        memo = [[-1] * (k+1) for _ in range(n)]\n",
    "\n",
    "        return dp(dst, k) # 倒序的嘛，从终点向起点倒着递归\n",
    "    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        edges = [[] for _ in range(n)]\n",
    "        for f, t, p in flights:\n",
    "            edges[f].append([t, p])\n",
    "\n",
    "        de = deque([[src, 0]])\n",
    "        finded1 = [inf for _ in range(n)]\n",
    "        finded1[src] = 0\n",
    "        while de and k > -1:\n",
    "            finded2 = [a for a in finded1]\n",
    "\n",
    "            for _ in range(len(de)):\n",
    "                now, nowp = de.pop()\n",
    "                for child, p in edges[now]:\n",
    "                    if finded1[child] > p + finded1[now]:\n",
    "                        finded2[child] = min(p + finded1[now], finded2[child])\n",
    "                        de.appendleft([child, finded2[child]])\n",
    "            finded1 = finded2\n",
    "\n",
    "            k -= 1\n",
    "\n",
    "        return finded1[dst] if finded1[dst] != inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        connect = defaultdict(dict)\n",
    "        for a, b, c in flights:\n",
    "            connect[a][b] = c\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(city, remain):\n",
    "            if city == dst:\n",
    "                return 0\n",
    "            if not remain:\n",
    "                return inf\n",
    "            remain -= 1\n",
    "            ans = inf\n",
    "            for nxt in connect[city]:\n",
    "                ans = min(ans, dfs(nxt, remain) + connect[city][nxt])\n",
    "            return ans\n",
    "        \n",
    "        res = dfs(src, k + 1)\n",
    "        return res if res != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        # 将中转站个数转化成边的条数\n",
    "        k += 1\n",
    "        self.src = src\n",
    "        self.dst = dst\n",
    "        self.graph = [[] for _ in range(n)]\n",
    "        for f in flights:\n",
    "            start = f[0]\n",
    "            end = f[1]\n",
    "            weight = f[2]\n",
    "            self.graph[start].append([end, weight])\n",
    "\n",
    "        return self.dijkstra(src, dst, k, self.graph)\n",
    "\n",
    "    def dijkstra(self, src, dst, k, graph: List[List[int]]):\n",
    "        \"\"\"\n",
    "        输⼊⼀个起点 src，计算从 src 到其他节点的最短距离\n",
    "        :param start:\n",
    "        :param graph:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        import heapq\n",
    "        v = len(graph)\n",
    "        # dp table，distTo[i]可理解为节点s到节点i的最短路劲，后续要不停地更新该表\n",
    "        # 定义：从起点 src 到达节点 i 的最短路径权重为 distTo[i]\n",
    "        # 定义：从起点 src 到达节点 i 的最⼩权重路径⾄少要经过 nodeNumTo[i] 个节点\n",
    "        distTo = [float('inf')] * v\n",
    "        nodeNumTo = [float('inf')] * v\n",
    "        # base case\n",
    "        distTo[src] = 0\n",
    "        nodeNumTo[src] = 0\n",
    "\n",
    "        min_heap = []\n",
    "        # 从起点s开始BFS\n",
    "        heapq.heappush(min_heap, self.State(src, 0, 0))\n",
    "\n",
    "        while min_heap:\n",
    "            curState = heapq.heappop(min_heap)\n",
    "            curNodeID = curState.id\n",
    "            curCostFromStart = curState.costFromStart\n",
    "            curNodeNumFromStart = curState.nodeNumFromStart\n",
    "\n",
    "            # 找到最短路径\n",
    "            if curNodeID == dst:\n",
    "                return curCostFromStart\n",
    "\n",
    "            # 中转次数耗尽\n",
    "            if curNodeNumFromStart == k:\n",
    "                continue\n",
    "\n",
    "            # 遍历curNodeID的相邻节点\n",
    "            for neighbor in graph[curNodeID]:\n",
    "                nextNodeID = neighbor[0]\n",
    "                costToNextNode = curCostFromStart + neighbor[1]\n",
    "                nextNodeNumFromSrc = curNodeNumFromStart + 1\n",
    "\n",
    "                # 剪枝，如果中转次数更多，花费还更⼤，那必然不会是最短路径\n",
    "                if costToNextNode > distTo[nextNodeID] and \\\n",
    "                    nextNodeNumFromSrc > nodeNumTo[nextNodeID]:\n",
    "                    continue\n",
    "\n",
    "                if costToNextNode < distTo[nextNodeID]:\n",
    "                    # 更新dp table\n",
    "                    distTo[nextNodeID] = costToNextNode\n",
    "                    nodeNumTo[nextNodeID] = nextNodeNumFromSrc\n",
    "\n",
    "                    # 将该邻居节点加入优先级队列\n",
    "                heapq.heappush(min_heap, self.State(nextNodeID, costToNextNode, nextNodeNumFromSrc))\n",
    "\n",
    "        return -1\n",
    "\n",
    "    class State:\n",
    "        def __init__(self, id, costFromStart, nodeNumFromStart):\n",
    "            \"\"\"\n",
    "            :param id: 图节点的 id\n",
    "            :param costFromStart: 从 src 节点到当前节点的花费\n",
    "            :param nodeNumFromStart: 从 src 节点到当前节点经过的节点个数\n",
    "            \"\"\"\n",
    "            self.id = id\n",
    "            self.costFromStart = costFromStart\n",
    "            self.nodeNumFromStart = nodeNumFromStart\n",
    "\n",
    "        def __lt__(self, other):\n",
    "            if self.costFromStart < other.costFromStart:\n",
    "                return True\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        w = defaultdict(dict)\n",
    "        for a, b, wt in flights:\n",
    "            w[a][b] = wt\n",
    "        # can't use dijkstra, cause that stops before get to dst\n",
    "        # using floyd instead\n",
    "        @cache\n",
    "        def dfs(cur, step):\n",
    "            if cur == dst:\n",
    "                return 0\n",
    "            if step < 0:\n",
    "                return inf\n",
    "            step -= 1\n",
    "            ans = inf\n",
    "            for nxt in w[cur].keys():\n",
    "                ans = min(ans, dfs(nxt, step) + w[cur][nxt])\n",
    "            return ans\n",
    "        res = dfs(src, k)\n",
    "        return res if res < inf else -1\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        Map = {}\n",
    "        for st,end,p in flights:\n",
    "            if st in Map:\n",
    "                Map[st].append([end,p])\n",
    "            else:\n",
    "                Map[st] = [[end,p]]\n",
    "        \n",
    "        pq = []\n",
    "        pq.append([0,src,k+1])\n",
    "        visted = {}\n",
    "        while pq:\n",
    "            dis,index,stopnum = heapq.heappop(pq)\n",
    "            if index == dst:\n",
    "                return dis\n",
    "            visted[index] = [dst,stopnum]\n",
    "            if stopnum > 0:\n",
    "                if index in Map:\n",
    "                    for nxt,p in Map[index]:\n",
    "                        if nxt not in visted or visted[nxt][1] < stopnum-1: \n",
    "                            heapq.heappush(pq,[p+dis,nxt,stopnum-1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from math import *\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        edges=defaultdict(list)\n",
    "        for [u,v,p] in flights:\n",
    "            edges[u].append((u,v,p))\n",
    "        min_price=[inf]*n\n",
    "        # print('edges:', edges)\n",
    "        min_price[src]=0\n",
    "        q=deque(edges[src])\n",
    "        step=0\n",
    "        while q:\n",
    "            buff=[]\n",
    "            for i in range(len(q)):\n",
    "                u,v,p=q.popleft()\n",
    "                if min_price[u]+p<min_price[v]:\n",
    "                    buff.append((v,min_price[u]+p))\n",
    "                    q.extend(edges[v])\n",
    "            for v,p in buff:\n",
    "                min_price[v]=min(min_price[v],p)\n",
    "            step+=1\n",
    "            if step>k:\n",
    "                break\n",
    "        return -1 if isinf(min_price[dst]) else min_price[dst]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        node={}\n",
    "        price={}\n",
    "        visited={}\n",
    "        if src==dst:\n",
    "            return 0\n",
    "        for i in range(n):\n",
    "            node[i]=[i]\n",
    "            price[(i,i)]=0\n",
    "        for i in flights:\n",
    "            node[i[0]].append(i[1])\n",
    "            price[(i[0],i[1])]=i[2]\n",
    "        if k<1:\n",
    "            for f in flights:\n",
    "                if f[0]==src and f[1]==dst:\n",
    "                    return f[2]\n",
    "            return -1\n",
    "        visited=[[-1 for i in range(n+1)] for _ in range(n+1)]\n",
    "        for u in range(n):\n",
    "            for v in range(n):\n",
    "                if (u,v) in price:\n",
    "                    visited[u][v]=price[(u,v)]\n",
    "        for i in range(k):\n",
    "            visited2=[[i for i in j]  for j in visited]\n",
    "            for u in range(n):\n",
    "                for v in range(n):\n",
    "                    if visited[u][v]==-1:\n",
    "                        continue\n",
    "                    for z in node[v]:\n",
    "                        if visited[u][z]==-1 or visited[u][v]+price[(v,z)]<visited2[u][z]:\n",
    "                            if visited[u][v]==-1:\n",
    "                                continue\n",
    "                            visited2[u][z]=visited[u][v]+price[(v,z)]\n",
    "            visited=[[i for i in j]  for j in visited2]\n",
    "            #print(visited[src][dst])\n",
    "        return visited[src][dst]\n",
    "                        \n",
    "        \n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        # 将中转站个数转化成边的条数\n",
    "        k += 1\n",
    "        self.src = src\n",
    "        self.dst = dst\n",
    "        self.graph = [[] for _ in range(n)]\n",
    "        for f in flights:\n",
    "            start = f[0]\n",
    "            end = f[1]\n",
    "            weight = f[2]\n",
    "            self.graph[start].append([end, weight])\n",
    "\n",
    "        return self.dijkstra(src, dst, k, self.graph)\n",
    "\n",
    "    def dijkstra(self, src, dst, k, graph: List[List[int]]):\n",
    "        \"\"\"\n",
    "        输⼊⼀个起点 src，计算从 src 到其他节点的最短距离\n",
    "        :param start:\n",
    "        :param graph:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        import heapq\n",
    "        v = len(graph)\n",
    "        # dp table，distTo[i]可理解为节点s到节点i的最短路劲，后续要不停地更新该表\n",
    "        # 定义：从起点 src 到达节点 i 的最短路径权重为 distTo[i]\n",
    "        # 定义：从起点 src 到达节点 i 的最⼩权重路径⾄少要经过 nodeNumTo[i] 个节点\n",
    "        distTo = [float('inf')] * v\n",
    "        nodeNumTo = [float('inf')] * v\n",
    "        # base case\n",
    "        distTo[src] = 0\n",
    "        nodeNumTo[src] = 0\n",
    "\n",
    "        min_heap = []\n",
    "        # 从起点s开始BFS\n",
    "        heapq.heappush(min_heap, self.State(src, 0, 0))\n",
    "\n",
    "        while min_heap:\n",
    "            curState = heapq.heappop(min_heap)\n",
    "            curNodeID = curState.id\n",
    "            curCostFromStart = curState.costFromStart\n",
    "            curNodeNumFromStart = curState.nodeNumFromStart\n",
    "\n",
    "            # 找到最短路径\n",
    "            if curNodeID == dst:\n",
    "                return curCostFromStart\n",
    "\n",
    "            # 中转次数耗尽\n",
    "            if curNodeNumFromStart == k:\n",
    "                continue\n",
    "\n",
    "            # if curCostFromStart > distTo[curNodeID]:\n",
    "            #     # 已经有一条更短的路径到达curNode节点了\n",
    "            #     continue\n",
    "\n",
    "            # 遍历curNodeID的相邻节点\n",
    "            for neighbor in graph[curNodeID]:\n",
    "                nextNodeID = neighbor[0]\n",
    "                costToNextNode = curCostFromStart + neighbor[1]\n",
    "                nextNodeNumFromSrc = curNodeNumFromStart + 1\n",
    "\n",
    "                # 剪枝，如果中转次数更多，花费还更⼤，那必然不会是最短路径\n",
    "                if costToNextNode > distTo[nextNodeID] and \\\n",
    "                    nextNodeNumFromSrc > nodeNumTo[nextNodeID]:\n",
    "                    continue\n",
    "\n",
    "                if costToNextNode < distTo[nextNodeID]:\n",
    "                    # 更新dp table\n",
    "                    distTo[nextNodeID] = costToNextNode\n",
    "                    nodeNumTo[nextNodeID] = nextNodeNumFromSrc\n",
    "\n",
    "                    # 将该邻居节点加入优先级队列\n",
    "                heapq.heappush(min_heap, self.State(nextNodeID, costToNextNode, nextNodeNumFromSrc))\n",
    "\n",
    "        return -1\n",
    "\n",
    "    class State:\n",
    "        def __init__(self, id, costFromStart, nodeNumFromStart):\n",
    "            \"\"\"\n",
    "            :param id: 图节点的 id\n",
    "            :param costFromStart: 从 src 节点到当前节点的花费\n",
    "            :param nodeNumFromStart: 从 src 节点到当前节点经过的节点个数\n",
    "            \"\"\"\n",
    "            self.id = id\n",
    "            self.costFromStart = costFromStart\n",
    "            self.nodeNumFromStart = nodeNumFromStart\n",
    "\n",
    "        def __lt__(self, other):\n",
    "            if self.costFromStart < other.costFromStart:\n",
    "                return True\n",
    "            return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from heapq import heappush\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        visited = {}\n",
    "        queue = [[0, src, 0]]\n",
    "        adj = collections.defaultdict(list)\n",
    "\n",
    "        visited[src] = k+2\n",
    "        for fr, to, w in flights:\n",
    "            adj[fr].append([to, w])\n",
    "        \n",
    "        while queue:\n",
    "            price, node, step = heappop(queue)\n",
    "            if step > k+1:\n",
    "                continue\n",
    "            if node in visited and step >= visited[node]:\n",
    "                continue\n",
    "            visited[node] = step\n",
    "            if node == dst:\n",
    "                return price\n",
    "            for to, w in adj[node]:\n",
    "                heappush(queue, [price+w, to, step+1])\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        cache = dict()\n",
    "\n",
    "        def traverse(start, count):\n",
    "            # if count < -1:\n",
    "            #     return sys.maxsize\n",
    "            \n",
    "            if start == dst:\n",
    "                return 0\n",
    "            \n",
    "            if count < 0:\n",
    "                return sys.maxsize\n",
    "            \n",
    "            key = (start, count)\n",
    "            if key in cache:\n",
    "                return cache[key]\n",
    "            \n",
    "            min_price = sys.maxsize\n",
    "            for f, t, p in flights:\n",
    "                if f != start:\n",
    "                    continue\n",
    "                price = traverse(t, count - 1)\n",
    "                if price < sys.maxsize:\n",
    "                    min_price = min(min_price, price + p)\n",
    "            cache[key] = min_price\n",
    "            return min_price\n",
    "        \n",
    "        res = traverse(src, k)\n",
    "        return res if res < sys.maxsize else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        mp = defaultdict(dict)\n",
    "        seen = set()\n",
    "        for start, end, price in flights:\n",
    "            seen.add(end)\n",
    "            mp[start][end] = price\n",
    "        if dst not in seen:\n",
    "            return -1\n",
    "        @cache\n",
    "        def dfs(k, src):\n",
    "            if src == dst:\n",
    "                return 0\n",
    "            if k < 0:\n",
    "                return inf\n",
    "            ans = inf\n",
    "            for nxt in mp[src]:\n",
    "                ans = min(ans, dfs(k - 1, nxt) + mp[src][nxt])\n",
    "            return ans\n",
    "        cheapest = dfs(k, src)\n",
    "        return cheapest if cheapest != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from math import *\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        edges=defaultdict(list)\n",
    "        for [u,v,p] in flights:\n",
    "            edges[u].append((u,v,p))\n",
    "        min_price=[inf]*n\n",
    "        # print('edges:', edges)\n",
    "        min_price[src]=0\n",
    "        q=deque(edges[src])\n",
    "        step=0\n",
    "        while q:\n",
    "            #print('!', step, k)\n",
    "            buff=[]\n",
    "            for i in range(len(q)):\n",
    "                u,v,p=q.popleft()\n",
    "                #print(u,v,p)\n",
    "                #print('#', min_price[u],p,min_price[v])\n",
    "                if min_price[u]+p<min_price[v]:\n",
    "                    buff.append((v,min_price[u]+p))\n",
    "                    q.extend(edges[v])\n",
    "            #print('buff',buff)\n",
    "            for v,p in buff:\n",
    "                min_price[v]=min(min_price[v],p)\n",
    "            #print('Step', step, min_price)\n",
    "            step+=1\n",
    "            if step>k:\n",
    "                break\n",
    "        return -1 if isinf(min_price[dst]) else min_price[dst]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        dic = defaultdict(dict)\n",
    "        destinations = set()\n",
    "        for start, end, price in flights:\n",
    "            destinations.add(end)\n",
    "            dic[start][end] = price\n",
    "        if dst not in destinations:\n",
    "            return -1\n",
    "        @cache\n",
    "        def findCheapestPrice(k, src):\n",
    "            if src == dst:\n",
    "                return 0\n",
    "            if k < 0:\n",
    "                return inf\n",
    "            ans = inf\n",
    "            for nxt in dic[src]:\n",
    "                ans = min(ans, findCheapestPrice(k - 1, nxt) + dic[src][nxt])\n",
    "            return ans\n",
    "        cheapest = findCheapestPrice(k, src)\n",
    "        return cheapest if cheapest != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        edges = collections.defaultdict(list)\n",
    "        for flight in flights:\n",
    "            edges[flight[0]].append((flight[1], flight[2]))\n",
    "        res = {}\n",
    "        q = []\n",
    "        q.append((src, 0))\n",
    "        cur_k = 0\n",
    "        while q:\n",
    "            sz = len(q)\n",
    "            for i in range(sz):\n",
    "                d, p = q.pop(0)\n",
    "                old_p = res.get(d, float('inf'))\n",
    "                if p < old_p:\n",
    "                    res[d] = p\n",
    "                    for edge in edges[d]:\n",
    "                        q.append((edge[0], edge[1]+p))\n",
    "            cur_k += 1\n",
    "            if cur_k > k + 1:\n",
    "                break\n",
    "        return res.get(dst, -1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        graph = dict()\n",
    "        # 构建一个方便操作的地图\n",
    "        # start, end, price\n",
    "        for s, e, p in flights:\n",
    "            if not s in graph:\n",
    "                graph[s] = [[s, e, p]]\n",
    "            else:\n",
    "                graph[s].append([s, e, p])\n",
    "\n",
    "        # 记录我们去过的地方，格式为[城市，步数] = 价格\n",
    "        seen = dict()\n",
    "        seen[(src, 0)] = 0\n",
    "\n",
    "        # bfs\n",
    "        queue = graph.get(src, None)\n",
    "        cnt = 1 # 这里我们用走了多少步来表示，即走1步=中转0次\n",
    "        ans = []\n",
    "        while queue and cnt<=k+1:\n",
    "            tmp = []\n",
    "            for s,e,p in queue:\n",
    "                if not (e, cnt) in seen:\n",
    "                    seen[(e, cnt)] = seen[(s, cnt-1)] + p\n",
    "                    tmp += graph.get(e,[])\n",
    "                else:\n",
    "                    # 剪枝：来过e，当小于历史值的时候才更新，加入到队列，否则直接丢弃\n",
    "                    if seen[(s, cnt-1)]+p < seen[(e, cnt)]:\n",
    "                        seen[(e, cnt)] = seen[(s, cnt-1)]+p\n",
    "                        tmp += graph.get(e,[])\n",
    "                # 如果e就是我们要去的地方，记录一下走了cnt次的当前最佳\n",
    "                if e == dst:\n",
    "                    ans.append(seen[(e, cnt)])\n",
    "            queue = tmp\n",
    "            cnt += 1\n",
    "\n",
    "        return -1 if not ans else min(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "\n",
    "        f = [[float('inf')] * (k+2) for _ in range(n)]\n",
    "        g = defaultdict(list)\n",
    "        for [a,b,w] in flights:\n",
    "            g[a].append((b, w))\n",
    "        \n",
    "        def djkstra(s):\n",
    "            vis = [[0] * (k+2) for _ in range(n)]\n",
    "            f[s][0] = 0\n",
    "\n",
    "            Q = [(f[s][0], s, 0)]\n",
    "            while Q:\n",
    "                d, u, step = heapq.heappop(Q)\n",
    "                if step == k+1:\n",
    "                    continue \n",
    "                if vis[u][step]:\n",
    "                    continue \n",
    "                vis[u][step] = 1\n",
    "                for v,w in g[u]:\n",
    "                    if f[v][step+1] > f[u][step] + w:\n",
    "                        f[v][step+1] = f[u][step] + w\n",
    "                        heapq.heappush(Q,(f[v][step+1], v, step+1))\n",
    "\n",
    "        djkstra(src)\n",
    "        ans = float('inf')\n",
    "        for x in range(k+2):\n",
    "            ans = min(ans, f[dst][x]) \n",
    "        \n",
    "        return ans if ans < float('inf') else -1 \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Cell:\n",
    "    def __init__(self,node,stop,price):\n",
    "        self.node = node\n",
    "        self.stop = stop\n",
    "        self.price = price\n",
    "\n",
    "    def __lt__(self,other):\n",
    "        return self.price<other.price\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        def gen_graph():\n",
    "            g = defaultdict(list)\n",
    "            for fr,to,p in flights:\n",
    "                g[fr].append((to,p))\n",
    "            return g\n",
    "\n",
    "        graph = gen_graph()\n",
    "        q = [Cell(src,0,0)]\n",
    "        visited = {}\n",
    "        while q:\n",
    "            cur = heappop(q)\n",
    "            if cur.node in visited and cur.stop>=visited[cur.node]:\n",
    "                continue\n",
    "            visited[cur.node] = cur.stop\n",
    "            if cur.node==dst:\n",
    "                return cur.price\n",
    "            if cur.stop>=k+1:\n",
    "                continue\n",
    "            for nei,p in graph[cur.node]:\n",
    "                heappush(q,Cell(nei,cur.stop+1,p+cur.price))\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        indgrees, memo = dict(), dict()\n",
    "        for flight in flights:\n",
    "            f, t, p = flight[0], flight[1], flight[2]\n",
    "            if t not in indgrees:\n",
    "                indgrees[t] = []\n",
    "            indgrees[t].append((f, p))\n",
    "\n",
    "        def dp(s: int, k: int) -> int:\n",
    "            if s == src:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return float('inf')\n",
    "            if (s, k) in memo:\n",
    "                return memo[(s, k)]\n",
    "            ans = float('inf')\n",
    "            if s in indgrees:\n",
    "                for indgree in indgrees[s]:\n",
    "                    f, p = indgree[0], indgree[1]\n",
    "                    ans = min(ans, dp(f, k - 1) + p)\n",
    "            memo[(s, k)] = ans\n",
    "            return ans\n",
    "        ans = dp(dst, k+1)\n",
    "        return ans if ans != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        # 定义：从 src 出发，k 步之内到达 s 的最短路径权重\n",
    "        def dp(s, k):\n",
    "            #base case\n",
    "            if s == src:  # 从 src 到 src，一步都不用走\n",
    "                return 0\n",
    "            if k == 0: # 如果步数用尽，就无解了\n",
    "                return -1\n",
    "            key = str(s) + \"-\" +str(k)\n",
    "            if key in memo:\n",
    "                return memo[key]\n",
    "            res = float(\"inf\")\n",
    "            if s in indegree:\n",
    "                for v in indegree[s]:#从后往前，自顶向下分解\n",
    "                    from_, price = v\n",
    "                    # 从 src 到达相邻的入度节点所需的最短路径权重\n",
    "                    subProblem = dp(from_, k - 1)\n",
    "                    # 跳过无解的情况\n",
    "                    if subProblem != -1:\n",
    "                        res = min(res, subProblem + price )\n",
    "            memo[key] = -1  if res == float(\"inf\") else res\n",
    "            return memo[key]\n",
    "\n",
    "        \n",
    "        memo = {}\n",
    "        k += 1 #k = 1 走两步\n",
    "        indegree = {}\n",
    "        for f in flights:\n",
    "            from_, to, price = f\n",
    "            if to not in indegree:\n",
    "                indegree[to] = []\n",
    "            indegree[to].append([from_, price])\n",
    "            \n",
    "        return dp(dst, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for f,t,p in flights:\n",
    "            g[f].append((t,p))\n",
    "        dist = [[inf]*(k + 2) for _ in range(n)]\n",
    "        dist[src][0] = 0\n",
    "        q = [(0,0,src)]\n",
    "        ans = inf\n",
    "        while q:\n",
    "            d,cnt,u = heappop(q)\n",
    "            if dist[u][cnt] < d:\n",
    "                continue\n",
    "            if u == dst:\n",
    "                ans = min(ans,d)\n",
    "            else:\n",
    "                for v,p in g[u]:\n",
    "                    if cnt + 1 <= k + 1 and dist[u][cnt] + p < dist[v][cnt + 1]:\n",
    "                        dist[v][cnt + 1] = dist[u][cnt] + p \n",
    "                        heappush(q,(dist[u][cnt] + p,cnt + 1,v))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        grid_dic = defaultdict(set)\n",
    "        price_dic = defaultdict(int)\n",
    "        for f,t,p in flights:\n",
    "            grid_dic[f].add(t)\n",
    "            price_dic[(f,t)] = p\n",
    "        visited = defaultdict(int)\n",
    "        heap = [[0,src,k+1]]\n",
    "        while heap:\n",
    "            res,start,cnt = heapq.heappop(heap)\n",
    "            if start == dst:\n",
    "                return res\n",
    "            for u in grid_dic[start]:\n",
    "                if cnt <= 0:\n",
    "                    continue\n",
    "                if (u,cnt) not in visited or visited[(u,cnt)] > res+price_dic[(start,u)]:\n",
    "                    visited[(u,cnt)] = res+price_dic[(start,u)]\n",
    "                    heapq.heappush(heap,[res+price_dic[(start,u)],u,cnt-1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# BFS+剪枝\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        graph = dict()\n",
    "        # 构建一个方便操作的地图\n",
    "        # start, end, price\n",
    "        for s, e, p in flights:\n",
    "            if not s in graph:\n",
    "                graph[s] = [[s, e, p]]\n",
    "            else:\n",
    "                graph[s].append([s, e, p])\n",
    "\n",
    "        # 记录我们去过的地方，格式为[城市，步数] = 价格\n",
    "        seen = dict()\n",
    "        seen[(src, 0)] = 0\n",
    "\n",
    "        # bfs\n",
    "        queue = graph.get(src, None)\n",
    "        cnt = 1 # 这里我们用走了多少步来表示，即走1步=中转0次\n",
    "        ans = []\n",
    "        while queue and cnt<=k+1:\n",
    "            tmp = []\n",
    "            for s,e,p in queue:\n",
    "                if not (e, cnt) in seen:\n",
    "                    seen[(e, cnt)] = seen[(s, cnt-1)] + p\n",
    "                    tmp += graph.get(e,[])\n",
    "                else:\n",
    "                    # 剪枝：来过e，当小于历史值的时候才更新，加入到队列，否则直接丢弃\n",
    "                    if seen[(s, cnt-1)]+p < seen[(e, cnt)]:\n",
    "                        seen[(e, cnt)] = seen[(s, cnt-1)]+p\n",
    "                        tmp += graph.get(e,[])\n",
    "                # 如果e就是我们要去的地方，记录一下走了cnt次的当前最佳\n",
    "                if e == dst:\n",
    "                    ans.append(seen[(e, cnt)])\n",
    "            queue = tmp\n",
    "            cnt += 1\n",
    "\n",
    "        return -1 if not ans else min(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\r\n",
    "    \r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for f, t, p in flights:\r\n",
    "            g[f].append((t, p))  \r\n",
    "\r\n",
    "        q = [(src, 0)]\r\n",
    "        s = set(q)\r\n",
    "        step = 0 \r\n",
    "        res = inf \r\n",
    "        while q and step <= k + 1:\r\n",
    "            tmp = q \r\n",
    "            q = []\r\n",
    "            for x, dis in tmp:\r\n",
    "                if x == dst:\r\n",
    "                    res = min(res, dis)\r\n",
    "                else:\r\n",
    "                    for y, p in g[x]:\r\n",
    "                        if p + dis < res and (y, p + dis) not in s:\r\n",
    "                            q.append((y, p + dis))\r\n",
    "                            s.add((y, p + dis))\r\n",
    "            step += 1\r\n",
    "        return res if res < inf else -1 \r\n",
    "\r\n",
    "            \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# BFS+剪枝\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        graph = dict()\n",
    "        # 构建一个方便操作的地图\n",
    "        # start, end, price\n",
    "        for s, e, p in flights:\n",
    "            if not s in graph:\n",
    "                graph[s] = [[s, e, p]]\n",
    "            else:\n",
    "                graph[s].append([s, e, p])\n",
    "\n",
    "        # 记录我们去过的地方，格式为[城市，步数] = 价格\n",
    "        seen = dict()\n",
    "        seen[(src, 0)] = 0\n",
    "\n",
    "        # bfs\n",
    "        queue = graph.get(src, None)\n",
    "        cnt = 1 # 这里我们用走了多少步来表示，即走1步=中转0次\n",
    "        ans = []\n",
    "        while queue and cnt<=k+1:\n",
    "            tmp = []\n",
    "            for s,e,p in queue:\n",
    "                if not (e, cnt) in seen:\n",
    "                    seen[(e, cnt)] = seen[(s, cnt-1)] + p\n",
    "                    tmp += graph.get(e,[])\n",
    "                else:\n",
    "                    # 剪枝：来过e，当小于历史值的时候才更新，加入到队列，否则直接丢弃\n",
    "                    if seen[(s, cnt-1)]+p < seen[(e, cnt)]:\n",
    "                        seen[(e, cnt)] = seen[(s, cnt-1)]+p\n",
    "                        tmp += graph.get(e,[])\n",
    "                # 如果e就是我们要去的地方，记录一下走了cnt次的当前最佳\n",
    "                if e == dst:\n",
    "                    ans.append(seen[(e, cnt)])\n",
    "            queue = tmp\n",
    "            cnt += 1\n",
    "\n",
    "        return -1 if not ans else min(ans)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        grid_dic = defaultdict(set)\n",
    "        price_dic = defaultdict(int)\n",
    "        for f,t,p in flights:\n",
    "            grid_dic[f].add(t)\n",
    "            price_dic[(f,t)] = p\n",
    "        visited = defaultdict(int)\n",
    "        heap = [[0,src,k+1]]\n",
    "        while heap:\n",
    "            res,start,cnt = heapq.heappop(heap)\n",
    "            \n",
    "            if start == dst:\n",
    "                return res\n",
    "            for u in grid_dic[start]:\n",
    "                if cnt <= 0:\n",
    "                    continue\n",
    "                if (u,cnt) not in visited or visited[(u,cnt)] > res+price_dic[(start,u)]:\n",
    "                    visited[(u,cnt)] = res+price_dic[(start,u)]\n",
    "                    heapq.heappush(heap,[res+price_dic[(start,u)],u,cnt-1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, lst):\n",
    "        self.dst = lst[0]\n",
    "        self.price = lst[1]\n",
    "    def __lt__(self, other):\n",
    "        if self.price == other.price:\n",
    "            return self.dst < other.dst\n",
    "        else:\n",
    "            return self.price < other.price\n",
    "# BFS + Dijkstra\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        import heapq\n",
    "        import collections\n",
    "        cost = 0\n",
    "        path = 0\n",
    "        res = float(\"inf\")\n",
    "        dic = collections.defaultdict(list)\n",
    "        heap = []\n",
    "        for f in flights:\n",
    "            dic[f[0]].append([f[1], f[2]])\n",
    "\n",
    "        heap.append([cost, src, path]) # heap 注意是[[]]的格式\n",
    "        heapq.heapify(heap)\n",
    "        visted = [n+1] * n # ?\n",
    "        while heap:\n",
    "            c, dis, p = heapq.heappop(heap)\n",
    "            if dis == dst: # 这个要写在continue之前，否在会报错\n",
    "                #res = min(res, c) # 不用每次再取最小值，因为heap中堆顶总是花费最少的，所以遇到终点直接返回\n",
    "                return c\n",
    "            if p >= visted[dis] or p > k: # ?\n",
    "                continue\n",
    "            \n",
    "            visted[dis] = p\n",
    "            for l in dic[dis]:\n",
    "                heapq.heappush(heap, [c+l[1], l[0], p+1])\n",
    "        #if res == float('inf'):\n",
    "        return -1\n",
    "        #return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        # 整理所有航班之间的联系\n",
    "        flights_info={}\n",
    "        for f in flights:\n",
    "            s = f[0]\n",
    "            d = f[1]\n",
    "            price = f[2]\n",
    "            if s not in flights_info:\n",
    "                flights_info[s]=[]\n",
    "            flights_info[s].append({\"to\":d, 'price':price})\n",
    "\n",
    "        def traverse(src: int, dst: int, k: int, record: dict) -> int:\n",
    "            if k<0:\n",
    "                return 99999999\n",
    "\n",
    "            if src==dst:\n",
    "                return 0\n",
    "                \n",
    "            key = str(src)+'to'+str(k)\n",
    "            # print(src, dst, k, key, record)\n",
    "            if key in record:\n",
    "                return record[key]\n",
    "\n",
    "            cost = 99999999\n",
    "            # 遍历从src出发的所有情况\n",
    "            for flight in flights_info.get(src, []):\n",
    "                to = flight[\"to\"]\n",
    "                price = flight[\"price\"]\n",
    "                next_trip = traverse(to, dst, k-1, record)\n",
    "                cost = min(cost, price+next_trip)\n",
    "\n",
    "            record[key] = cost\n",
    "            return record[key]\n",
    "\n",
    "        # print(flights_info)\n",
    "        minimum_cost=traverse(src, dst, k+1, {})\n",
    "\n",
    "        return -1 if minimum_cost==99999999 else minimum_cost\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        cost = {}\n",
    "        graph = defaultdict(list)\n",
    "        for x,y,c in flights:\n",
    "            graph[x].append(y)\n",
    "            cost[(x,y)] = c\n",
    "\n",
    "        visited = set()\n",
    "        visited.add((src, 0))\n",
    "        stops = -1\n",
    "        res = math.inf \n",
    "        # (node, cost)\n",
    "        q = deque([(src, 0)])\n",
    "        while q:\n",
    "            if stops > k:\n",
    "                break\n",
    "            # curlevel, all node with same stop \n",
    "            for _ in range(len(q)):\n",
    "                curnode, curcost = q.popleft()\n",
    "                if stops <= k and curnode == dst:\n",
    "                    res = min(res, curcost)\n",
    "                for nxtnode in graph[curnode]:\n",
    "                    # Key Point --- \n",
    "                    # early cut, we only keep the node with lower cost\n",
    "                    # And for repeated node, we only keep its lowest cost\n",
    "                    newcost = curcost+cost[(curnode,nxtnode)]\n",
    "                    qitem = (nxtnode,newcost)\n",
    "                    if (res == math.inf or newcost < res) and (qitem not in visited): \n",
    "                        q.append(qitem)\n",
    "                        visited.add(qitem)\n",
    "            stops += 1\n",
    "        return -1 if res == math.inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        # Create adjacency list\n",
    "        adj_list = [[] for _ in range(n)]\n",
    "        for fromi, toi, pricei in flights:\n",
    "            adj_list[fromi].append((toi, pricei))\n",
    "        \n",
    "        # Dijkstra's with priority queue: (cost, current node, stops)\n",
    "        q = [(0, src, 0)]\n",
    "        \n",
    "        # Use 2D visited list: visited[i][j] = cost to visit node i with j stops\n",
    "        visited = [[float('inf')] * (k+2) for _ in range(n)]\n",
    "\n",
    "        while q:\n",
    "            price, cur, stops = heapq.heappop(q)\n",
    "\n",
    "            # If we reach the destination, return the price\n",
    "            if cur == dst:\n",
    "                return price\n",
    "            \n",
    "            # If this route is worse than a previously found route with the same or fewer stops, skip it\n",
    "            if price >= visited[cur][stops]:\n",
    "                continue\n",
    "\n",
    "            visited[cur][stops] = price\n",
    "\n",
    "            # If stops exceed the limit, continue\n",
    "            if stops > k:\n",
    "                continue\n",
    "\n",
    "            # Visit all neighbors\n",
    "            for next_node, wt in adj_list[cur]:\n",
    "                # If this route is promising, push it to the queue\n",
    "                if price + wt < visited[next_node][stops+1]:\n",
    "                    heapq.heappush(q, (price + wt, next_node, stops + 1))\n",
    "                        \n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        cost = {}\n",
    "        graph = defaultdict(list)\n",
    "        for x,y,c in flights:\n",
    "            graph[x].append(y)\n",
    "            cost[(x,y)] = c\n",
    "\n",
    "        root = (src, 0)\n",
    "        visited = set()\n",
    "        visited.add(root)\n",
    "        stops = -1\n",
    "        res = math.inf \n",
    "        # (node, cost)\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            if stops > k:\n",
    "                break\n",
    "            # curlevel, all node with same stop \n",
    "            for _ in range(len(q)):\n",
    "                curnode, curcost = q.popleft()\n",
    "                if stops <= k and curnode == dst:\n",
    "                    res = min(res, curcost)\n",
    "                for nxtnode in graph[curnode]:\n",
    "                    # Key Point --- \n",
    "                    # early cut, we only keep the node with lower cost\n",
    "                    # And for repeated node, we only keep its lowest cost\n",
    "                    newcost = curcost+cost[(curnode,nxtnode)]\n",
    "                    qitem = (nxtnode,newcost)\n",
    "                    if newcost < res and qitem not in visited: \n",
    "                        q.append(qitem)\n",
    "                        visited.add(qitem)\n",
    "            stops += 1\n",
    "        return -1 if res == math.inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for f,t,p in flights:\n",
    "            graph[f].append([t,p])\n",
    "        heap = [[0,0,src]]\n",
    "        dp = {}\n",
    "        while len(heap)>0:\n",
    "            cost,cnt,f = heapq.heappop(heap)\n",
    "            if cnt<=k+1 and f==dst:\n",
    "                return cost\n",
    "            if cnt>=k+1:\n",
    "                continue\n",
    "            \n",
    "            for t,p in graph[f]:\n",
    "                if (t,cnt+1) in dp and dp[(t,cnt+1)]<=cost+p:\n",
    "                    continue \n",
    "                \n",
    "                dp[(t,cnt+1)] = cost+p\n",
    "                heapq.heappush(heap,[cost+p,cnt+1,t])\n",
    "    \n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        cost = {}\n",
    "        graph = defaultdict(list)\n",
    "        for x,y,c in flights:\n",
    "            graph[x].append(y)\n",
    "            cost[(x,y)] = c\n",
    "\n",
    "        visited = set()\n",
    "        visited.add((src, 0))\n",
    "        stops = -1\n",
    "        res = math.inf \n",
    "        # (node, cost)\n",
    "        q = deque([(src, 0)])\n",
    "        while q:\n",
    "            if stops > k:\n",
    "                break\n",
    "            # curlevel, all node with same stop \n",
    "            for _ in range(len(q)):\n",
    "                curnode, curcost = q.popleft()\n",
    "                if stops <= k and curnode == dst:\n",
    "                    res = min(res, curcost)\n",
    "                for nxtnode in graph[curnode]:\n",
    "                    # Key Point --- \n",
    "                    # early cut, we only keep the node with lower cost\n",
    "                    # And for repeated node, we only keep its lowest cost\n",
    "                    newcost = curcost+cost[(curnode,nxtnode)]\n",
    "                    qitem = (nxtnode,newcost)\n",
    "                    if newcost < res and qitem not in visited: \n",
    "                        q.append(qitem)\n",
    "                        visited.add(qitem)\n",
    "            stops += 1\n",
    "        return -1 if res == math.inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice1(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:\n",
    "\n",
    "        g = dict()\n",
    "\n",
    "        for e in flights:\n",
    "            g.setdefault(e[0], set()).add((e[1], e[2]))\n",
    "        \n",
    "        self.rslt = float('INF')\n",
    "        cache = dict()\n",
    "\n",
    "        def bfs(e, cost, k):\n",
    "            if k < 0:\n",
    "                return\n",
    "            if e == dst:\n",
    "                self.rslt = min(cost, self.rslt)\n",
    "                return\n",
    "\n",
    "            if e not in g:\n",
    "                return\n",
    "\n",
    "            for n in g[e]:\n",
    "                bfs(n[0], cost + n[1], k - 1)\n",
    "\n",
    "\n",
    "        bfs(src, 0, K + 1)\n",
    "        if self.rslt == float('INF'):\n",
    "            return -1\n",
    "        return self.rslt\n",
    "\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:\n",
    "        import queue\n",
    "\n",
    "        g = dict()\n",
    "        q = queue.PriorityQueue()\n",
    "        for f  in flights:\n",
    "            g.setdefault(f[0], dict()).setdefault(f[1], f[2])\n",
    "        q.put((0, src, K + 1))\n",
    "        while not q.empty():\n",
    "            node = q.get()\n",
    "            if node[1] == dst:\n",
    "                return node[0]\n",
    "            if node[2] - 1 < 0:\n",
    "                continue\n",
    "            if node[1] not in g:\n",
    "                continue\n",
    "            for k, v in g[node[1]].items():\n",
    "                q.put((node[0] + v, k, node[2] - 1))\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        conn = collections.defaultdict(set)\n",
    "        for u, v, w in flights:\n",
    "            conn[u].add((v, w))\n",
    "        pool = [(0, -1, src)]    # (cost, stop, city)\n",
    "        seen = {(-1, src): 0}    # (stop, city): cost\n",
    "        res = float('inf')\n",
    "        while pool:\n",
    "            cost, stop, city = heapq.heappop(pool)\n",
    "            if city == dst:\n",
    "                res = min(res, cost)\n",
    "                continue\n",
    "            if stop == k:\n",
    "                continue\n",
    "            for v, w in conn[city]:\n",
    "                if (stop+1, v) not in seen or seen[stop+1, v] > cost + w:\n",
    "                    heapq.heappush(pool, (cost+w, stop+1, v))\n",
    "                    seen[stop+1, v] = cost + w\n",
    "        return -1 if res == float('inf') else res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        self.destinations = set()\n",
    "        self.graph = self.construct_graph(flights)\n",
    "        self.dst = dst\n",
    "        if dst not in self.destinations:\n",
    "            return -1\n",
    "        ans = self.dfs(src,k)\n",
    "        if ans == float(\"inf\"):\n",
    "            return -1\n",
    "        return ans\n",
    "\n",
    "    def construct_graph(self,flights):\n",
    "        graph = defaultdict(list)\n",
    "        for i,j,price in flights:\n",
    "            self.destinations.add(j)\n",
    "            graph[i].append([j,price])\n",
    "        return graph\n",
    "    @lru_cache(None)\n",
    "    def dfs(self,src,k):\n",
    "        if src == self.dst:\n",
    "            return 0\n",
    "        if k < 0:\n",
    "            return float(\"inf\")\n",
    "        ans = float(\"inf\")\n",
    "        for next,price in self.graph[src]:\n",
    "            ans = min (ans, self.dfs(next,k-1) + price)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        dic=collections.defaultdict(list)\n",
    "        for s,e,c in flights:\n",
    "            dic[s].append((e,c))\n",
    "        #print(dic)\n",
    "        q=[(0,0,src)]\n",
    "        _max=10**9\n",
    "        ct=[[_max]*(k+1) for _ in range(n)]\n",
    "        import heapq as h\n",
    "        while q:\n",
    "            #print(q)\n",
    "            c,step,s=h.heappop(q)\n",
    "            if s==dst:\n",
    "                return c\n",
    "            if step>k:\n",
    "                continue\n",
    "            if c<ct[s][step]:\n",
    "                ct[s][step]=c\n",
    "                for e,c1 in dic[s]:\n",
    "                    h.heappush(q,(c+c1,step+1,e))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "\n",
    "BIG = 10**9+7\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "\n",
    "        ans = BIG\n",
    "        edge = [[] for _ in range(n)]\n",
    "        for i, j, p in flights:\n",
    "            edge[i].append([j, p])\n",
    "        stack = [[0, 0, src]]\n",
    "        visit = [BIG]*n\n",
    "        while stack:\n",
    "            cost, cnt, i = heapq.heappop(stack)\n",
    "            if cnt <= k+1 and i == dst:\n",
    "                if cost < ans:\n",
    "                    ans = cost\n",
    "                continue\n",
    "\n",
    "            if cnt == k+1 or visit[i]<cnt:\n",
    "                continue\n",
    "            visit[i] = cnt\n",
    "            for j, p in edge[i]:\n",
    "                heapq.heappush(stack, [cost+p, cnt+1, j])\n",
    "        return ans if ans < BIG else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        memo = [[-1 for _ in range(k+1)] for _ in range(n)]\n",
    "        @cache\n",
    "        def dp(i,k):\n",
    "            fee = 0\n",
    "            if i == dst :\n",
    "                return 0\n",
    "            if k == -1:\n",
    "                return float('inf')\n",
    "            if memo[i][k] != -1:\n",
    "                return memo[i][k]\n",
    "            min_fee = float('inf')\n",
    "            for from_i,to_i,price_i in flights:\n",
    "                if from_i == i:\n",
    "                    fee_i = dp(to_i,k-1) + price_i\n",
    "                    if fee_i<min_fee:\n",
    "                        min_fee = fee_i\n",
    "                else:\n",
    "                    continue\n",
    "            fee += min_fee\n",
    "            memo[i][k] = fee\n",
    "            return fee            \n",
    "        ans = 0\n",
    "        ans = dp(src,k)\n",
    "        return -1 if ans == float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        d = defaultdict(list)\n",
    "        for flight in flights:\n",
    "            d[flight[0]] += [flight[1:]]\n",
    "        ans = []\n",
    "        @cache\n",
    "        def dp(x, count):\n",
    "            if count > k: return float('inf')\n",
    "            ans = float('inf')\n",
    "            for dist, price in d[x]:\n",
    "                if dist == dst: \n",
    "                    ans = min(ans, price)\n",
    "                else: \n",
    "                    ans = min(ans, price + dp(dist, count+1))\n",
    "            return ans\n",
    "        ans = dp(src, 0)\n",
    "        return -1 if ans == float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        from collections import defaultdict\n",
    "        hashmap = defaultdict(list)\n",
    "        for from_i,to_i,price_i in flights:\n",
    "            hashmap[from_i].append([to_i,price_i])\n",
    "        @cache\n",
    "        def dp(i,k):\n",
    "            fee = 0\n",
    "            if i == dst :\n",
    "                return 0\n",
    "            if k == -1:\n",
    "                return float('inf')\n",
    "            min_fee = float('inf')\n",
    "            for [to_i,price_i] in hashmap[i]:\n",
    "                fee_i = dp(to_i,k-1) + price_i\n",
    "                if fee_i<min_fee:\n",
    "                    min_fee = fee_i\n",
    "                else:\n",
    "                    continue\n",
    "            fee += min_fee\n",
    "            return fee            \n",
    "        ans = 0\n",
    "        ans = dp(src,k)\n",
    "        return -1 if ans == float('inf') else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        k += 1\n",
    "        grid = [[] for _ in range(n + 1)]\n",
    "\n",
    "        for a,b,v in flights:\n",
    "            grid[a].append((b,v))\n",
    "\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur : int,k : int) -> int: \n",
    "            res = float('inf')\n",
    "            if k < 0:\n",
    "                return res\n",
    "\n",
    "            if cur == dst:\n",
    "                return 0\n",
    "\n",
    "            for x,d in grid[cur]:\n",
    "                res = min(res,d + dfs(x,k - 1))\n",
    "            \n",
    "            return res\n",
    "        \n",
    "        res = dfs(src,k)\n",
    "\n",
    "        if res > 1e9:\n",
    "            return -1\n",
    "        else:\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from functools import cache\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:    \n",
    "        all_flights = defaultdict(list)\n",
    "        costs = dict()\n",
    "        for s, d, p in flights:\n",
    "            all_flights[s].append(d)\n",
    "            costs[(s, d)] = p\n",
    "        \n",
    "        @cache\n",
    "        def dp(curr_pos, flights_left):\n",
    "            if flights_left < 0:\n",
    "                return float('inf')\n",
    "            if curr_pos == dst:\n",
    "                return 0\n",
    "\n",
    "            return min(\n",
    "                (\n",
    "                    dp(transfer, flights_left-1) + costs[(curr_pos, transfer)]\n",
    "                    for transfer in all_flights[curr_pos]\n",
    "                ),\n",
    "                default=float('inf')\n",
    "            )\n",
    "        \n",
    "        tmp = dp(src, k+1)\n",
    "        if tmp < float('inf'):\n",
    "            return tmp\n",
    "        else:\n",
    "            return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq \n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        \n",
    "        ad=collections.defaultdict(list)\n",
    "        for s,e,w in flights:\n",
    "            ad[s].append([e,w])\n",
    "        \n",
    "        heap=[]\n",
    "        hq.heappush(heap,[0,src,-1])\n",
    "        vis=set()\n",
    "        while heap:\n",
    "            d,cur,change=hq.heappop(heap)\n",
    "          #  print(d,change)\n",
    "            if (cur,change) in vis:\n",
    "                continue\n",
    "            vis.add((cur,change))\n",
    "            if change>k:\n",
    "                continue\n",
    "            if cur==dst:\n",
    "                return  d \n",
    "            for nex,nexd in ad[cur]:\n",
    "                newd=d+nexd\n",
    "                if change+1<=k and (nex,change+1) not in vis:\n",
    "                    hq.heappush(heap,[newd,nex,change+1])\n",
    "                \n",
    "\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        d = {}\n",
    "        for f in flights:\n",
    "            d[(f[0],f[1])] = f[2]\n",
    "        stod = {}\n",
    "        for f in flights:\n",
    "            if f[0] not in stod:\n",
    "                temp = []\n",
    "                temp.append(f[1])\n",
    "                stod[f[0]] = temp\n",
    "            else:\n",
    "                stod[f[0]].append(f[1])\n",
    "        MAX = 1000001\n",
    "        @cache\n",
    "        def DFS(s,l):\n",
    "            if s==dst and l<=k+1:\n",
    "                return 0\n",
    "            if l>k+1 or not stod.get(s,0):\n",
    "                return MAX\n",
    "            res = MAX\n",
    "            for t in stod[s]:\n",
    "                res = min(res,DFS(t,l+1)+d[(s,t)])\n",
    "            return res\n",
    "        res = DFS(src,0)\n",
    "        return res if res<MAX else -1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        neis = collections.defaultdict(set)\n",
    "        edges = {}\n",
    "        max_val = 1\n",
    "        for f, t, p in flights:\n",
    "            neis[f].add(t)\n",
    "            edges[(f, t)] = p\n",
    "            max_val += p\n",
    "        def dfs(node, step, memo = {}):\n",
    "            if step <= -1 and node != dst:\n",
    "                return max_val\n",
    "            if node == dst:\n",
    "                return 0\n",
    "            if (node, step) not in memo:\n",
    "                arr = [dfs(nei, step-1) + edges[(node, nei)] for nei in neis[node]]\n",
    "                memo[(node, step)] = min(arr) if arr != [] else max_val\n",
    "            return memo[(node, step)]\n",
    "        return dfs(src, k) if dfs(src, k) < max_val else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        graph = collections.defaultdict(list)\n",
    "        weights = {} \n",
    "\n",
    "        for edge in flights:\n",
    "            frm, to, cost = edge\n",
    "            graph[frm].append(to)\n",
    "            weights[(frm, to)] = cost\n",
    "\n",
    "        minHeap = [] # (cost, node, transfer)\n",
    "        heapq.heappush(minHeap, (0, src, 0))\n",
    "        visited = set()\n",
    "\n",
    "        while minHeap:\n",
    "            cost, node, t = heapq.heappop(minHeap)\n",
    "            if node == dst:\n",
    "                return cost \n",
    "            if (node, t) in visited:\n",
    "                continue\n",
    "            if t > k:\n",
    "                continue\n",
    "            visited.add((node, t))\n",
    "            for neighbor in graph[node]:\n",
    "                if (neighbor, k+1) not in visited:\n",
    "                    curCost = cost + weights[(node, neighbor)]\n",
    "                    heapq.heappush(minHeap, (curCost, neighbor, t+1))\n",
    "\n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        d = {}\n",
    "        for f in flights:\n",
    "            d[(f[0],f[1])] = f[2]\n",
    "        stod = {}\n",
    "        for f in flights:\n",
    "            if f[0] not in stod:\n",
    "                temp = []\n",
    "                temp.append(f[1])\n",
    "                stod[f[0]] = temp\n",
    "            else:\n",
    "                stod[f[0]].append(f[1])\n",
    "        print(stod)\n",
    "        MAX = 1000001\n",
    "        @cache\n",
    "        def DFS(s,l):\n",
    "            if s==dst and l<=k+1:\n",
    "                return 0\n",
    "            if l>k+1:\n",
    "                return MAX\n",
    "            if not stod.get(s,0):\n",
    "                return MAX\n",
    "            res = MAX\n",
    "            for t in stod[s]:\n",
    "                res = min(res,DFS(t,l+1)+d[(s,t)])\n",
    "            return res\n",
    "        res = DFS(src,0)\n",
    "        return res if res<MAX else -1\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        f = defaultdict(list)\n",
    "        for from_, to, price in flights:\n",
    "            f[to].append((from_, price))\n",
    "        k += 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(s: int, k: int) -> int:\n",
    "            if s == src:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return -1\n",
    "            ans = inf\n",
    "            if s in f:\n",
    "                for from_, price in f[s]:\n",
    "                    sub = dfs(from_, k - 1)\n",
    "                    if sub != -1:\n",
    "                        ans = min(ans, sub + price)\n",
    "            return -1 if ans == inf else ans\n",
    "        \n",
    "        return dfs(dst, k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v, w in flights:\n",
    "            g[u].append((v,w))\n",
    "        \n",
    "        @cache\n",
    "        def dfs(s, cnt):\n",
    "            if s == dst:\n",
    "                return 0\n",
    "            if cnt > k:\n",
    "                return inf\n",
    "            u = g[s]\n",
    "            res = inf\n",
    "            for v, w in u:\n",
    "                res = min(res, dfs(v, cnt + 1) + w)\n",
    "            return res\n",
    "        ans = dfs(src, 0)\n",
    "        return ans if ans != inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for f, t, c in flights:\n",
    "            g[t].append((f, c))\n",
    "        @cache\n",
    "        def dfs(i, k):\n",
    "            if k < 0:\n",
    "                return inf\n",
    "            if i == src:\n",
    "                return 0\n",
    "            res = inf\n",
    "            for pre, c in g[i]:\n",
    "                res = min(res, dfs(pre, k - 1) + c)\n",
    "            return res\n",
    "        ans = dfs(dst, k + 1)  # 最多“经过”k站，所以最后一站不算，k+1\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, k: int) -> int:\n",
    "        dic = defaultdict(list)\n",
    "        for ele in flights:\n",
    "            dic[ele[1]].append([ele[0], ele[2]])\n",
    "        @cache\n",
    "        def dp(s, k):\n",
    "            if s == src:\n",
    "                return 0\n",
    "            if k == 0:\n",
    "                return -1\n",
    "            res = float(\"inf\")\n",
    "            if s in dic:\n",
    "                for ele in dic[s]:\n",
    "                    fro = ele[0]\n",
    "                    pri = ele[1]\n",
    "                    sub = dp(fro, k - 1)\n",
    "                    if sub != -1:\n",
    "                        res = min(res, pri + sub)\n",
    "            \n",
    "            return -1 if res == float(\"inf\") else res\n",
    "        return dp(dst, k + 1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
